# -*- coding: utf-8 -*-
"""
Created on Sun Oct 28 00:05:45 2018

@author: Administrator
"""

class LNode:
    def __init__(self, element, next_ = None):
        self.element = element
        self.next = next_
        

#node = LNode(5)
#print(node)
#print(node.getElement())
#print(node.getNext())
class LinkedList:

    def __init__(self):
        self.head = None
    
    def isEmpty(self):
        return self.head is None
    
     # 创建一个链表
    def createList(self, elements):
 
        if len(elements) >= 1:
            node1 = LNode(elements[0])
            if len(elements) < 2:
                return self.head
            # 循环创建节点并连接
            self.head = p = node1
            for index in range(1,len(elements)):
                node = LNode(elements[index])
                p.next = node
                p = node
        # 返回链表头指针
        return self.head
    
    def length(self):
        p = self.head
        count = 0
        while p is not None:
            count += 1
            p = p.next
        return count
    
    def prepend(self, element):
        if self.head is None:
            self.head = LNode(element)
        node = LNode(element, self.head)
        self.head = node
    
    def append(self, element):
        
        p = self.head
        # 如果没有元素
        if p is None:
            self.head = LNode(element)
            return
        # 遍历到链尾
        while p.next is not None:
            p = p.next
        p.next = LNode(element)
    
    def insert(self, element, index):
        
        if index < 0 or index > self.length():
            raise ValueError("arguments error!")
            
        p = self.head
        # 如果没有元素
        if p is None:
            self.head = LNode(element)
            return 
        for i in range(1, index):
            p = p.next
        p.next = LNode(element, p.next)    
        
    def deleteFirst(self):
        # 头删法
        if self.head is None:
            return
        self.head = self.head.next
        
    def deleteLast(self):
        # 尾删法
        if self.head is None:
            return
        # 遍历到倒数第二个元素
        p = self.head
        for i in range(0, self.length() - 2):
            p = p.next
            
        p.next = None
        
    
    # 未完成
    def delete(self, index):
        # 如果没有元素，直接返回
        if self.head is None:
            return
        # 如果只有一个元素
        if self.head.next is None:
            self.head = None
            return
        # 如果有2个及以上时
        p = self.head
#        count = 0
        while p.next is not None:
            pass
#            if index-1 == count:
#                p.next = None
#                return
#            p = p.next
#            count += 1
            
    
    def search(self, element):
        
        p = self.head
        if p is None:
            return
        count = 0
        while p is not None:
            if p.element == element:
                return count
            p = p.next
            count += 1
   
    
    def printAll(self):
        p = self.head
        while p is not None:
            print(p.element)
            p = p.next


if __name__ == "__main__":
    # 测试createList()
    linkedList = LinkedList()
    test = [1,2,3,4]
#    print(linkedList.createList(test))
#    linkedList.printAll()
    
    # 测试prepend()
#    linkedList.prepend(5)  # 没元素时，头插法
#    linkedList.printAll()
#    linkedList.createList(test)
#    linkedList.prepend(5) # 有元素时
#    linkedList.printAll()
    
    # 测试append()
#    linkedList.createList(test)
#    linkedList.append(5)
#    print("length: %d" % linkedList.length())
#    linkedList.printAll()
    
    # 测试insert()
#    linkedList.insert(5,0)
#    linkedList.printAll()
#    linkedList.createList(test)
#    linkedList.insert(5,1)
#    linkedList.insert(5,2)
#    linkedList.printAll()
    
    # 测试deleteFirst()
#    linkedList.createList(test)
#    linkedList.deleteFirst()
#    linkedList.printAll()
    
    # 测试deleteLast()
#    linkedList.createList(test)
#    linkedList.deleteLast()
#    linkedList.printAll()
    
    # 测试search()
#    linkedList.createList(test)
#    print(linkedList.search(4))
